package com.example.linked.doublepointers;

import com.example.linked.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * 存在一个按升序排列的链表，给你这个链表的头节点 head ，
 * 请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
 * 输入：head = [1,2,3,3,4,4,5]
 * 输出：[1,2,5]
 *
 */
public class Leetcode82_DeleteDuplicates {
    public static void main(String[] args) {
        // 1,1,2,2,3,3,4,5,6,6
        ListNode head = new ListNode(1);
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(3);
        ListNode node5 = new ListNode(3);
        ListNode node6 = new ListNode(4);
        ListNode node7 = new ListNode(5);
        ListNode node8 = new ListNode(6);
        ListNode node9 = new ListNode(6);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;
        node8.next = node9;

        ListNode res = new Solution().deleteDuplicates(head);
        ListNode cur = res;
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.next;
        }
    }

    static class Solution {

        /**
         * 解法二:
         * 双指针法
         *
         * @param head
         * @return
         */
        public ListNode deleteDuplicates2(ListNode head) {
            if(head==null || head.next==null) {
                return head;
            }
            ListNode newHead = new ListNode(-1);// 定义一个不含数据的节点(哑结点)
            newHead.next = head;
            ListNode p = newHead;
            ListNode q = head;
            while(q != null && q.next != null) {
                // 初始化的时p指向的是哑结点，所以比较逻辑应该是p的下一个节点和q的下一个节点
                if(p.next.val != q.next.val) {
                    p = p.next;
                    q = q.next;
                } else {
                    //如果p、q指向的节点值相等，就不断移动q，直到p、q指向的值不相等
                    while(q != null && q.next != null && p.next.val == q.next.val) {
                        q = q.next;
                    }
                    p.next = q.next;
                    q = q.next;
                }
            }
            return newHead.next;
        }

        /**
         * 解法一:
         * 先将链表的相同元素删掉只剩一个并记录相同元素到set中
         * 然后再遍历一次将set中的元素全部删除
         * @param head
         * @return
         */
        public ListNode deleteDuplicates1(ListNode head) {
            if(head == null || head.next == null) {
                return head;
            }
            // 将链表的相同元素删掉只剩一个并记录相同元素到set中(方式一)
            ListNode p, q;
            Set<Integer> set = new HashSet<>();
            p = head;
            q = head.next;
            while (p != null && q != null) {
                if (p.val == q.val) {
                    while (q.next != null && q.val == q.next.val) { // q和q.next相同说明结尾指针还得后移
                        q = q.next;
                    }
                    // 退出内存循环说明q已经到了相同元素段的末尾，需要删除该段相同的元素
                    set.add(q.val);
                    q = q.next;
                    p.next = q;
                } else {
                    p = p.next;
                    q = q.next;
                }
            }

            // 将链表的相同元素删掉只剩一个并记录相同元素到set中(方式二)
//        ListNode cur = head;
//        while (cur != null && cur.next != null) {
//            if (cur.val == cur.next.val) {
//                cur.next = cur.next.next;
//                set.add(cur.val);
//            } else {
//                cur = cur.next;
//            }
//        }

            // 删除相同元素后头部有可能是重复元素需要循环处理
            while (head != null) {
                if (set.contains(head.val)) {
                    head = head.next;
                } else {
                    break;
                }
            }

            // 再遍历一次将set中的元素全部删除
            p = head;
            while (p != null && p.next != null) {
                if (set.contains(p.next.val)) {
                    p.next = p.next.next;
                }
                else {
                    p = p.next;
                }
            }

            return head;
        }


        public ListNode deleteDuplicates(ListNode head) {
            return deleteDuplicates1(head);
        }
    }
}
